// 1906. [合并区间] 服务器空闲时段
// https://oj.rnd.huawei.com/problems/1906/submissions
// 数据超大,溢出，建议使用差分，思路: 1. 合并同一台机器的空闲时段 2. 统计每一台
// =============================
//现有serverNum台服务器和taskNum项任务，并将任务按时段分配给各服务器，
//请你统计恰好有且只有一台服务器空闲的时段（注：“空闲”指没有任务在执行）。
//最后请输出排序后的空闲时段。说明：统计范围的最大时刻为当前用例的涉及的最大时刻。
//须合并连续的时段，如：[1,2]和[2,3]合并为[1,3]。按照时段的开始时刻的大小升序排序。
//若无满足要求的时段，输出区间-1 -1。
//输入 第一行一个整数 serverNum，表示服务器个数，取值范围 [1,10^4)
//第二行一个整数 taskNum，表示任务个数，取值范围 [1,10^4)
//接下来 taskNum 行，每行 3 个整数startTime endTime
// serverId，分别表示一个任务的开始时刻、结束时刻、服务器编号。取值范围：0 <
// startTime < endTime < 10^9， 1 <= serverId <= serverNum 输出
//每行两个整数，表示一个空闲时段，格式为：startTime endTime。 输入 3
// 5
// 1 2 1
// 1 3 1
// 5 6 1
// 2 3 2
// 5 6 3
//输出
// 2 3
// 5 6
//样例 1 解释，如下图所示：
// 1 号服务器总共分配了 3 项任务，2/3 号服务器各分配了 1 项任务，
//时段 [1, 2]： 1 号服务器在工作，2/3号服务器空闲，
//时段 [2, 3]： 1 号和 2 号服务器在工作，3 号服务器空闲，
//时段 [3, 5]： 3 台服务器都空闲，
//时段 [5, 6]： 1 号和 3 号服务器在工作，2 号服务器空闲，
//故满足要求的时段为 [2, 3] 和 [5, 6]。
//输入样例 2 复制
// 4
// 6
// 1 2 1
// 1 2 2
// 1 2 4
// 2 3 1
// 2 3 2
// 2 3 3
//输出样例 2
// 1 3
//提示样例 2
// 1/2 号服务器各分配了 2 项任务，3/4 号服务器各分配了 1 项任务，
//时段 [1, 2]： 1/2/4 号服务器在工作，3 号服务器空闲，
//时段 [2, 3]： 1/2/3 号服务器在工作，4 号服务器空闲，
//故满足要求的时段为 [1, 2] 和 [2, 3]，合并后为 [1, 3]
//输入 2
// 3
// 1 3 1
// 1 2 2
// 2 3 2
//输出 -1 -1
//提示 1 号服务器分配了 1 项任务，2 号服务器各分配了 2 项任务，
//时段 [1, 2]： 1/2 号服务器在工作，没有服务器空闲，
//时段 [2, 3]： 1/2 号服务器在工作，没有服务器空闲，
//故没有满足要求的时段，输出[-1, -1]。
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
//#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif
struct Section {
  int begin;
  int end;
  bool operator<(Section s1) const { return begin < s1.begin; }
};
//   ---------
//     -------
//   ----
class Solution {
 public:
  // 待实现函数，在此函数中填入答题代码  // 开始时刻、结束时刻、服务器编号   //
  // [1, 3)
  vector<pair<int, int>> GetOneFreeTime(int serverNum, int taskNum,
                                        const vector<vector<int>>& tasks_) {
    map<int, vector<Section>> mapServer;
    PF("\n\n  task=%d\n", tasks_.size());
    auto tasks(tasks_);
    std::sort(tasks.begin(), tasks.end(),
              [](vector<int> t1, vector<int> t2) { return t1[0] < t2[0]; });
    int nMaxEndTime = 0;
    for (auto ta : tasks) {
      mapServer[ta[2]].push_back({ta[0], ta[1]});
      nMaxEndTime = max(nMaxEndTime, ta[1]);
    }
    for (auto svr : mapServer) {
      vector<Section>& vtSec = svr.second;
      for (size_t i = 0; i < vtSec.size(); i++)
        PF("%d-%d:%d,  ", vtSec[i].begin, vtSec[i].end, svr.first);
      PF("\n");
    }
    vector<int> vtFree(nMaxEndTime + 2);  //
    for (auto svr : mapServer) {
      vector<Section>& vtSec = svr.second;
      PF("%d======\n", svr.first);
      for (auto se : vtSec) PF("b:%d-%d, ", se.begin, se.end);
      PF("\n");
      for (size_t i = 0; i < vtSec.size(); i++) {
        if (i + 1 < vtSec.size() && vtSec[i + 1].begin <= vtSec[i].end) {
          vtSec[i + 1].begin = vtSec[i].begin;
          vtSec[i + 1].end = max(vtSec[i].end, vtSec[i + 1].end);
          vtSec[i] = {0, 0};  // 删当前记录
        }
      }
      for (auto se : vtSec) PF("a:%d-%d, ", se.begin, se.end);
      PF("\n");
      // 统计
      PF("free=  ");
      for (auto se : vtSec) {
        for (int i = se.begin; i > 0 && i < se.end; i++) {
          vtFree[i]++;
          PF("[%d]=%d, ", i, vtFree[i]);
        }
      }
      PF("=============\n");
    }
    PF("====out====\n");
    for (int i = 1; i < vtFree.size(); i++) {
      PF("%2d, ", vtFree[i]);
      if (i > 0 && i % 10 == 0) PF("\n");
    }
    PF("\n");
    set<pair<int, int>> mapFree;
    for (int i = 1; i < vtFree.size(); i++) {
      if (vtFree[i] + 1 == serverNum) {
        int start = i;
        int end = i;
        for (i; i + 1 < vtFree.size() && vtFree[i + 1] + 1 == serverNum; i++) {
          end = i + 1;
        }
        mapFree.insert({start, end});
      }
    }
    vector<pair<int, int>> res;
    int i = 0;
    for (auto fe : mapFree) {
      res.push_back({fe.first, fe.second + 1});
      PF("free.%d-%d\n", fe.first, fe.second + 1);
      if (i > 0 && i % 10 == 0) PF("\n");
      i++;
    }
    PF("end.%d\n", res.size());
    return res;
  }
};
// 以下为考题输入输出框架，此部分代码不建议改动
inline int ReadInt() {
  int number;
  std::cin >> number;
  return number;
}
template <typename T>
inline std::vector<T> ReadVector(int size) {
  std::vector<T> objects(size);
  for (int i = 0; i < size; ++i) {
    std::cin >> objects[i];
  }
  return objects;
}
inline void WriteVector(const std::vector<pair<int, int>>& objects) {
  auto it = objects.begin();
  if (it == objects.end()) {
    return;
  }
  std::cout << it->first << ' ' << it->second;
  for (++it; it != objects.end(); ++it) {
    std::cout << endl << it->first << ' ' << it->second;
  }
  std::cout << std::endl;
}
int main1906() {
  int serverNum = ReadInt();
  int taskNum = ReadInt();
  vector<vector<int>> tasks(taskNum);
  for (int i = 0; i < taskNum; ++i) {
    tasks[i] = ReadVector<int>(3);
  }
  Solution solu;
  auto result = solu.GetOneFreeTime(serverNum, taskNum, tasks);
  if (result.empty()) {
    cout << "-1 -1";
  } else {
    WriteVector(result);
  }
  return 0;
}